package com.lx.algorithm.monotoneStack;

import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-07 13:42:23
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-07     张李鑫                     1.0         1.0 Version
 */
public class AllTimesMinToMax {

    /**
     * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
     * 一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
     * 那么所有子数组中，这个值最大是多少？
     */


    public static int max(int[] arr) {
        int[] sumArr = new int[arr.length];
        sumArr[0] = arr[0];

        //获取累加和数组
        for (int i = 1; i < arr.length; i++) {
            sumArr[i] = arr[i] + sumArr[i - 1];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            //只要大于等于都去弹出
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                Integer pop = stack.pop();
                int sum = stack.isEmpty() ? sumArr[i-1] : sumArr[i - 1] - sumArr[stack.peek()];
                max = Math.max(sum * arr[pop], max);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            int rightSum = stack.isEmpty() ? sumArr[arr.length - 1] : sumArr[arr.length - 1] - sumArr[stack.peek()];
            max = Math.max(rightSum * arr[pop], max);
        }
        return max;
    }

    public static int max1(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int minNum = Integer.MAX_VALUE;
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                    minNum = Math.min(minNum, arr[k]);
                }
                max = Math.max(max, minNum * sum);
            }
        }
        return max;
    }

    public static int[] gerenareRondomArray() {
        int[] arr = new int[(int) (Math.random() * 20) + 10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 101);
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 2000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = gerenareRondomArray();
            if (max1(arr) != max(arr)) {
                System.out.println("FUCK!");
                break;
            }
        }
        System.out.println("test finish");
    }


}
